package com.demo.example.hot100;

public class TheLongestPalindrome {
    public static void main(String[] args) {
        long start=System.currentTimeMillis();
        System.out.println(findTheLongestPalindrome("babad"));
        long end=System.currentTimeMillis();
        System.out.println(end-start);

    }
     //  暴力解法 O(n^2)
    public static String longestPalindrome(String s){
        if(s==null){
            return null;
        }
        if(s.length()==1){
            return s;
        }
        String res=new String();
        for(int i=0;i<s.length();i++){
            StringBuilder stringBuilder=new StringBuilder();
            stringBuilder.append(s.charAt(i));
            for(int j=i+1;j<s.length();j++){
                stringBuilder.append(s.charAt(j));
                if(isPalindrome(stringBuilder.toString())){
                    if(stringBuilder.length()>res.length()){
                        res=stringBuilder.toString();
                    }
                }
            }
        }
        return res;
    }
    //判断是否是回文串的函数
    public static boolean isPalindrome(String s){
        StringBuilder sb=new StringBuilder(s);
        if(s.equals(sb.reverse().toString())){
            return true;
        }else{
            return false;
        }
    }
    //非暴力，双指针解法
    public static String findTheLongestPalindrome(String s){
        if(s==null){
            return null;
        }
        String res=new String();
        for(int i=0;i<s.length();i++){
            StringBuilder stringBuilder=new StringBuilder();
            stringBuilder.append(s.charAt(i));
            if(stringBuilder.length()>res.length()){
                res=stringBuilder.toString();
            }
            int left=i-1; //左指针
            int right=i+1; //右指针
            if(right<s.length() &&s.charAt(i)==s.charAt(right)){
                stringBuilder.append(s.charAt(right));
                right++;
            }
            while(left>=0 && right<s.length()){
                if(s.charAt(left)==s.charAt(right)){
                    stringBuilder.insert(0,s.charAt(left));
                    stringBuilder.append(s.charAt(right));
                    left--;
                    right++;
                }else{
                    break;
                }
            }
            if(stringBuilder.length()>res.length()){
                res=stringBuilder.toString();
            }
        }
        for(int i=0;i<s.length();i++){
            StringBuilder stringBuilder=new StringBuilder();
            stringBuilder.append(s.charAt(i));
            int left=i-1; //左指针
            int right=i+1; //右指针
            while(left>=0 && right<s.length()){
                if(s.charAt(left)==s.charAt(right)){
                    stringBuilder.insert(0,s.charAt(left));
                    stringBuilder.append(s.charAt(right));
                    left--;
                    right++;
                }else{
                    break;
                }
            }
            if(stringBuilder.length()>res.length()){
                res=stringBuilder.toString();
            }
        }
        return res;
    }
}
